package purchasePlans;

import java.util.Arrays;

public class Soluton {
//    public int purchasePlans(int[] nums, int target) {
//        // 二分查找
//        Arrays.sort(nums);
//        int ans = 0;
//        int MOD = 1000000007;
//        for (int i = 0; i < nums.length; i++) {
//            ans = (ans + binarySearch(nums,i+1,nums.length-1,target-nums[i]))%MOD;
//        }
//        return ans;
//    }
//    private int binarySearch(int[] nums,int l,int r,int target) {
//        int t = l;
//        while (l<=r) {
//            int mid = l+(r-l)/2;
//            if(nums[mid] <= target) {
//                l = mid+1;
//            }else {
//                r = mid-1;
//            }
//        }
//        return l-t;
//    }

    // 双指针
    public int purchasePlans(int[] nums, int target) {
        Arrays.sort(nums);
        int i = 0,j = nums.length-1,ans = 0,MOD = 1000000007;
        while (i<j) {
            if(nums[i] + nums[j] <= target) {
                // (i,i+1)(i,i+2),(i,i+3)...(i,j)都满足条件 所以ans+=(j-i);
                ans = (ans+(j-i))%MOD;
                i++; // i指针向右移动
            }else {
                j--;
                // j指针向左移动
            }
        }
        return ans;
    }
}
